package leetcode;

/**
 * leetcode 45题 跳跃游戏 II  medium
 */
public class LCode45 {
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        int jump = jump(nums);
        System.out.println(jump);
    }

    /**
     * 跳之前先计算跳的步数，每次记录跳的选项里跳的最远的位置，在这一条的结束的时候，更新一下下一次跳的最远的距离。
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            // 一次跳跃中的最远距离
            maxPosition = Math.max(maxPosition, i + nums[i]);
            // 开启下一步跳远
            if (i == end) {
                count++;
                end = maxPosition;
            }
        }
        return count;
    }
}
